package _2022.hot100._98_验证二叉搜索树;


import java.util.Deque;
import java.util.LinkedList;

/**
 * @author： YHSimon
 * @date： 2022-04-23 15:52
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        this.val = x;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {

    //递归中序遍历
    private int pre = Integer.MIN_VALUE;
    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }

        if (!isValidBST(root.left)) {
            return false;
        }

        if (root.val <= pre) {
            return false;
        }
        pre = root.val;
        return isValidBST(root.right);
    }

    //迭代中序遍历
    public boolean isValidBST2(TreeNode root){
        Deque<TreeNode> stack=new LinkedList<>();
        long pre=Long.MIN_VALUE;
        while(!stack.isEmpty()||root!=null){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }

            root=stack.pop();
            if(root.val<=pre){
                return false;
            }
            pre=root.val;
            root=root.right;
        }
        return true;
    }


    public static void main(String[] args) {
        Solution s = new Solution();
        TreeNode node=new TreeNode(5,new TreeNode(1),new TreeNode(4,new TreeNode(3),new TreeNode(6)));
        System.out.println(s.isValidBST(node));
    }
}
